package com.zjsru.plan2023.oneday;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @Author: CookLee
 * @Date: 2023/5/2
 *
 *  强整数
 *
 *  给定三个整数 x 、 y 和 bound ，返回 值小于或等于 bound 的所有 强整数 组成的列表 。
 *
 * 如果某一整数可以表示为 x^i + y^j ，其中整数 i >= 0 且 j >= 0，那么我们认为该整数是一个 强整数 。
 *
 * 你可以按 任何顺序 返回答案。在你的回答中，每个值 最多 出现一次。
 *
 *
 * 输入：x = 2, y = 3, bound = 10
 * 输出：[2,3,4,5,7,9,10]
 * 解释：
 * 2 = 2^0 + 3^0
 * 3 = 2^1 + 3^0
 * 4 = 2^0 + 3^1
 * 5 = 2^1 + 3^1
 * 7 = 2^2 + 3^1
 * 9 = 2^3 + 3^0
 * 10 = 2^0 + 3^2
 *
 */
public class PowerfulIntegers {
    
    private final Integer MAX_SQUARE_NUMBER = 21;
    
    /**
     * 强大整数,暴力枚举
     *
     * @param x     x
     * @param y     y
     * @param bound 绑定
     * @return {@link List}<{@link Integer}>
     */
    public List<Integer> powerfulIntegers(int x, int y, int bound) {
        Set<Integer> ans = new HashSet<>();
        //设置第一个加数
        int valueX = 1;
        //平方的乘数上限为21
        for (int i = 0; i < MAX_SQUARE_NUMBER; i++) {
            //设置第二个加数
            int valueY = 1;
            for (int j = 0; j < MAX_SQUARE_NUMBER; j++) {
                int sum = valueX + valueY;
                if (sum <= bound) {
                    ans.add(sum);
                } else {
                    //不符合要求的退出循环
                    break;
                }
                valueY = valueY * y;
            }
            if(valueX > bound){
                break;
            }
            valueX = valueX * x;
        }
        return new ArrayList<Integer>(ans);
    }
    
    public static void main(String[] args) {
        PowerfulIntegers powerfulIntegers = new PowerfulIntegers();
        int x = 2;
        int y = 3;
        int bound = 10;
        System.out.println(powerfulIntegers.powerfulIntegers(x, y, bound));
    }
    
}
